package com.bins.knowledge.point.algorithm;

import java.util.Arrays;

public class KnapsackProblemDP {

    public static int knapsack(int W, int[] weights, int[] values, int N) {
        // dp[i][j] 表示前 i 个物品，容量 j 时的最大价值
        int[][] dp = new int[N + 1][W + 1];

        for (int i = 1; i <= N; i++) {
            System.out.println(Arrays.deepToString(dp));
            System.out.println("+++++++++++++++++++++");
            for (int j = 1; j <= W; j++) {
                System.out.println(Arrays.deepToString(dp));
                System.out.println("------------------");
                if (weights[i - 1] > j) {
                    // 当前物品装不下，只能不选
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 选或不选，取最大值
                    dp[i][j] = Math.max(
                            dp[i - 1][j],
                            dp[i - 1][j - weights[i - 1]] + values[i - 1]
                    );
                }
            }
        }
        return dp[N][W]; // 最大价值
    }

    public static void main(String[] args) {
//        int W = 10; // 背包容量
//        int[] weights = {2, 3, 4, 5, 7}; // 物品重量
//        int[] values = {3, 4, 5, 6, 9};  // 物品价值
//        int W = 8; // 背包容量
//        int[] weights = {2, 3, 4, 5}; // 物品重量
//        int[] values = {3, 4, 5, 6};  // 物品价值
        int W = 8; // 背包容量
        int[] weights = {1}; // 物品重量
        int[] values = {1};  // 物品价值
        int N = weights.length;

        int maxValue = knapsack(W, weights, values, N);
        System.out.println("最大价值: " + maxValue); // 输出 10
    }
}
